\documentclass{report}
\usepackage[UTF8]{ctex}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{mathrsfs} %导入花体数学字母
\usepackage{caption}
\usepackage{graphicx, subfig} %插入图片
\usepackage{listings} %插入代码
\usepackage{xcolor} %语法高亮
\usepackage{fontspec} %字体包
\usepackage{diagbox} % 斜线表头
\usepackage{geometry} %设置页面
\usepackage{enumerate}
\usepackage[colorlinks,linkcolor=blue]{hyperref} %超链接
\usepackage{marginnote} % 在正文旁边添加注释文字

\setlength{\marginparwidth}{0.6in} %页边空白处设定宽度0.6英寸
\let\oldmarginpar\marginpar
\renewcommand\marginpar[1]{\-\oldmarginpar[\raggedleft\footnotesize\color{red} #1]%
	{\raggedright\footnotesize\color{red} #1}} % 注释文字用红色footnote 大小
\marginparsep = 10pt %与正文间隔10pt

% \marginpar{需要添加的内容}
% 显示或隐藏页边注释，只要在文件头添加下面的语句，把它注释掉后又显示页边内容
% \renewcommand{\marginpar}[2][]{}

\geometry{a4paper,left=2cm,right=2cm,top=2cm,bottom=2cm}

\usepackage{fancyhdr}
\usepackage{lipsum}
\pagestyle{fancy}

\renewcommand{\chaptermark}[1]{\markboth{#1}{}}
\renewcommand{\sectionmark}[1]{\markright{\arabic{section}.\ #1}}
\lhead[\thepage]{\leftmark} 
\rhead[\nouppercase{\rightmark}]{\thepage}

\lstset{
	columns=fixed,       
	numbers=left,                                        % 在左侧显示行号
	numberstyle=\color{black},                       % 设定行号格式
	basicstyle=\fontspec{Consolas}\small\color[RGB]{212,212,212},
	tabsize=4,
	frame=single,                                        % 背景边框
	rulecolor=\color[rgb]{0,0,0},                  % 边框颜色
	extendedchars=false,                                 % 解决换页问题
	backgroundcolor=\color[RGB]{30,30,30},            % 设定背景颜色
	keywordstyle=\color[RGB]{156,220,254},                 % 设定关键字颜色
	identifierstyle=\color[RGB]{86,156,214},                       % 普通标识符颜色
	commentstyle=\it\color[RGB]{106,153,73},                % 设置代码注释的格式
	stringstyle=\rmfamily\slshape\color[RGB]{206,145,91},   % 设置字符串格式
	showstringspaces=false,                              % 不显示字符串中的空格
	language=c++,                                        % 设置语言
	escapeinside=``,                                     % 逃逸字符
	xleftmargin=1em,                                     % 边距设置
	xrightmargin=1em, 
	aboveskip=1em
}

\title{{\Huge Homework1\\ 数值分析}}
\author{{\LARGE 3190105815 信息与计算科学\ 行一凡}}
\date{{\LARGE \today}}

\begin{document}
	\maketitle
	\section*{Exercise I}
	\begin{itemize}
		\item 由二分法的步骤，可得$ |b_n - a_n| = 2^{-n}|b_0 - a_0| $,故有第$ n $步间隔为$ 2^{-n}(3.5-1.5) = 2^{1-n}. $
		\item $ \forall c_n = (a_n+b_n)/2,\ |c_n-r|\le |b_n - a_n|/2 = 2^{-n}\le 1. $
	\end{itemize}

	\section*{Exercise II}
	\noindent 设$ \alpha $为根，需要$ \frac{|c_n-\alpha|}{\alpha}<\epsilon, $其中$ c_n =  (a_n+b_n)/2, $则有
	\begin{equation}\label{key}
		\dfrac{|c_n-\alpha|}{\alpha}\le	\dfrac{|b_n-a_n|}{2a_0} = \dfrac{b_0-a_0}{2^{n+1}a_0}<\epsilon.
	\end{equation}
	\begin{equation}\label{key}
		\begin{aligned}
			b_0-a_0 < 2^{n+1}a_0\epsilon
			&\Rightarrow log(b_0-a_0)<(n+1)log2+log\epsilon+loga_0\\ 
			&\Rightarrow n\le \dfrac{log(b_0-a_0)-log\epsilon-loga_0}{log2}-1
		\end{aligned}
	\end{equation}
	
	\section*{Exercise III}
	\noindent 直接带入迭代公式$ x_{n+1} = x_n - \frac{f(x_n)}{f^{\prime}(x_n)} $可得
	\begin{center}
		\begin{tabular}{|ccccc|}% 通过添加 | 来表示是否需要绘制竖线
			\hline
			$ x_0 $ & $ x_1 $ & $ x_2 $ & $ x_3 $ & $ x_4 $ \\ 
			\hline
			-1 & -0.8125 & -0.7708 & -0.7688 & -0.7688\\ 
			\hline % 在表格最下方绘制横线
		\end{tabular}
	\end{center}
	
	\section*{Exercise IV}
	\noindent 对$ f(\alpha) $泰勒展开则有
	\begin{equation}\label{key}
		0 = f(\alpha) = f(x_n) + f^{\prime}(\xi_n)(\alpha-x_n)
	\end{equation}
	\begin{equation}\label{key}
		|x_{n+1}-\alpha| = \left|x_n - \alpha - \dfrac{f(x_n)}{f^{\prime}(x_0)}\right| = \left|1-\dfrac{f(\xi_n)}{f^{\prime}(x_0)}\right||x_n - \alpha|
	\end{equation}
	\begin{equation}\label{key}
		e_{n+1} = \left|1-\dfrac{f(\xi_n)}{f^{\prime}(x_0)}\right|e_n
	\end{equation}
	故有$ C = \left|1-\frac{f(\xi_n)}{f^{\prime}(x_0)}\right|,\ s = 1. $
	
	\section*{Exercise V}
	\noindent 迭代序列$ \{x_n\} $不收敛，先考虑$ x>0, $令$ g(x) = tan^{-1}x, $则有
	\begin{equation}\label{key}
		g: (0,\dfrac{\pi}{2})\rightarrow (0,+\infty).
	\end{equation}
	\begin{equation}\label{key}
		g^{\prime}(x) = -\dfrac{1}{sin^2x},\ x\in (0,\dfrac{\pi}{2}).
	\end{equation}
	则$ \forall x,y\in (0,\dfrac{\pi}{2}),\ x < y $有
	\begin{equation}\label{key}
		\left|\dfrac{g(x)-g(y)}{x-y}\right| = |g^{\prime}(\xi)| > 1,\ \xi\in (x,y).
	\end{equation}
	反设迭代序列$ \{x_n\} $收敛,由$ x_{n+1} = g(x_n)$
	\begin{equation}\label{key}
		|x_{n+1}-x_n| = |g(x_n)-g(x_{n-1})| > |x_n-x_{n-1}|,\ \forall n>0.
	\end{equation}
	\begin{equation}\label{key}
		|x_{n+1}-x_n| > |x_1-x_0|.
	\end{equation}
	即除非初始值$ x_0 $恰好选为不动点，否则序列$ \{x_n\} $不可能收敛。
	对于$ x<0 $的情况同理可证。
	
	\section*{Exercise VI}
	\noindent 由题可得递推式$  x_n = \frac{1}{p+x_{n-1}},\ n>1 $,令$ g(x) = \frac{1}{p+x},\ x\in(0,+\infty) $,则有
	\begin{equation}\label{key}
		\left|\dfrac{g(x)-g(y)}{x-y}\right| =
		\left|\dfrac{\frac{1}{p+x}-\frac{1}{p+y}}{x-y}\right| = \left|\dfrac{1}{(p+x)(p+y)}\right| < \dfrac{1}{p^2} < 1.
	\end{equation}
	令$ \lambda = \frac{1}{p^2}, $则$ g(x) $满足
	\begin{equation}\label{key}
		|g(x)-g(y)| < \lambda|x-y|,\ \lambda < 1,\ \forall x,y\in (0,+\infty).
	\end{equation}
	故$ g(x) $为压缩映射，且有唯一不动点$ \alpha = \lim\limits_{n\to\infty}x_n > 0 $，则有
	\begin{equation}\label{key}
		\alpha = \dfrac{1}{p+\alpha}\Rightarrow \alpha = \sqrt{1+\frac{p^2}{4}}-\frac{p}{2}.
	\end{equation}
	
	\section*{Exercise VII}
	\noindent 当$ a_0<0<b_0 $时，相对误差无法估计，因此使用绝对误差$ |c_n-\alpha|<\epsilon $，可得
	\begin{equation}\label{key}
		|c_n-\alpha|\le	\dfrac{|b_n-a_n|}{2} = \dfrac{b_0-a_0}{2^{n+1}}<\epsilon.
	\end{equation}
	\begin{equation}\label{key}
		\begin{aligned}
			b_0-a_0 < 2^{n+1}\epsilon
			&\Rightarrow log(b_0-a_0)<(n+1)log2+log\epsilon\\ 
			&\Rightarrow n\le \dfrac{log(b_0-a_0)-log\epsilon}{log2}-1
		\end{aligned}
	\end{equation}
	由于当根$ \alpha $非常接近0时，相对误差变得非常大，因此无法准确估计其值。
	
	\section*{Exercise VIII}
	\begin{enumerate}[(1).] % []中设置序号样式
		\item 在$ \alpha $处展开$ f(x_n) $,得
		\begin{equation}\label{key}
			\begin{aligned}
				|f(x_n)| &=  \left|\sum_{i=1}^{k-1}\dfrac{(x_n-\alpha)^{i}}{i!}f^{(i)}(\alpha)+\dfrac{(x_n-\alpha)^{k}}{k!}f^{(k)}(\xi_n)\right|\\ 
				&= \left|\dfrac{(x_n-\alpha)^{k}}{k!}f^{(k)}(\xi_n)\right|
			\end{aligned}
		\end{equation}
		其中$ \xi_n $在$ x_n $和$ \alpha $之间。由$ f\in\mathcal{C}^{k+1},$ 当 $ x_n $充分接近 $ \alpha $时，
		\begin{equation}\label{key}
			\left|\dfrac{f(x_n)}{(x_n-\alpha)^{k}}\right| = \left|\dfrac{f^{(k)}(\alpha)}{k!}\right|
		\end{equation}
		因此，对足够大的$ n $,可以通过检测$ \left|\frac{f(x_n)}{(x_n-\alpha)^{k}}\right| $是否近似为常数判断多阶零点。
		\item 由初始条件，令$ f(x) = (x-\alpha)^kh(x),\ h(\alpha)\neq0,\ h^{\prime}(\alpha)\neq0,$则
		\begin{equation}\label{key}
			\begin{aligned}
				x_{n+1} &= x_n - k\dfrac{f(x_n)}{f^{\prime}(x_n)} = x_n - \dfrac{k(x_n-r)^kh(x_n)}{k(x_n-\alpha)^{k-1}h(x_n)+(x_n-\alpha)^kh^{\prime}(x_n)}\\ 
				&= x_n - \dfrac{k(x_n-\alpha)h(x_n)}{kh(x_n)+(x_n-\alpha)h^{\prime}(x_n)}\\ 
				&= \alpha - (x_n-\alpha)^2\dfrac{h^{\prime}(x_n)}{kh(x_n)+(x_n-\alpha)h^{\prime}(x_n)}
			\end{aligned}
		\end{equation}
		由$ f\in\mathcal{C}^{k+1},$则$ h\in\mathcal{C}^1 $,故在$ \alpha $的极小邻域有
		\begin{equation}\label{key}
			\left|\dfrac{x_{n+1}-\alpha}{(x_n-\alpha)^2}\right| = \left|\dfrac{h^{\prime}(x_n)}{kh(x_n)+(x_n-\alpha)h^{\prime}(x_n)}\right| < M
		\end{equation}
		先前的Theorem 1.15表明此时迭代公式具有二阶收敛性。
	\end{enumerate}
	
\end{document}